# -*- coding: utf-8 -*-
from __future__ import print_function

import sys
import os
import copy

reload(sys)
sys.setdefaultencoding("utf-8")

# 二叉树的前序遍历  pre  order traversal


# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 不使用递归的方式进行二叉树的中序遍历
# 中序遍历 根左右
def preorderTraversal(root):
    stack = []
    ans = []
    node = root
    while node or stack:
        while node:
            ans.append(node.val)
            stack.append(node)
            node = node.left
        node = stack.pop()
        node = node.right
    return ans


# 递归方式进行二叉树的遍历
def preorderTraversal_recursion(root):
    if root:
        return []
    else:
        return [root.val] + preorderTraversal_recursion(root.left) + preorderTraversal_recursion(root.right)



